import java.util.ArrayList;
import java.util.List;

public class Solution {

    /**
     * 给定一个正整数 n ，输出外观数列的第 n 项。
     * 「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。
     * 你可以将其视作是由递归公式定义的数字字符串序列：
     *
     * countAndSay(1) = "1"
     * countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。
     */
    public static String countAndSay(int n) {
        List<Integer> num = new ArrayList<>(30);
        num.add(1);
        List<Integer> appear = new ArrayList<>(30);
        List<Integer> tmp;
        int curIndex, cur, pre, count,time=1;

        while (time<n) {
            time++;
            //推算外观
            pre = num.get(0);
            count = 1;
            curIndex = 1;
            for (; curIndex < num.size(); curIndex++) {
                cur = num.get(curIndex);
                if (cur == pre) {
                    count++;
                } else {
                    appear.add(count);
                    appear.add(pre);
                    count = 1;
                    pre = cur;
                }
            }
            appear.add(count);
            appear.add(pre);

            //切换
            tmp = num;
            num = appear;
            appear = tmp;
            appear.clear();
        }

        StringBuilder sb = new StringBuilder();
        num.forEach(sb::append);

        return sb.toString();
    }

    public static void main(String[] args) {
        for (int i=1; i<7; i++){
            System.out.println(i + ":"+countAndSay(i));
        }
    }

}